class Solution
{
public:


    // 贪心法，解答错误，一些情况下不一定找到最优解ಠ_ಠ
    long long minimumTotalDistance(vector<int> &robot, vector<vector<int>> &factory)
    {
        int robotCount = robot.size();
        int factoryCount = factory.size();
        sort(robot.begin(), robot.end());
        sort(factory.begin(), factory.end());
        long long result = 0;
        unordered_set<int> repaired;

        using NearestRobots = priority_queue<vector<int>, vector<vector<int>>, Compare>;
        vector<NearestRobots> nearestRobots(factoryCount);
        for (int i = 0; i < factoryCount; ++i)
        {
            auto &heap = nearestRobots[i];
            for (int j = 0; j < robotCount; ++j)
            {
                heap.push({abs(robot[j] - factory[i][0]), j});
            }
        }

        while (repaired.size() < robotCount)
        {
            int minDistRobotID = -1;
            int minDistFactoryID = -1;
            int minDist = INT_MAX;
            for (int i = 0; i < factoryCount; ++i)
            {
                if (factory[i][1] == 0)
                {
                    continue;
                }
                auto nearestRobot = nearestRobots[i].top();
                if (nearestRobot[0] < minDist)
                {
                    minDist = nearestRobot[0];
                    minDistFactoryID = i;
                    minDistRobotID = nearestRobot[1];
                }
                else if (nearestRobot[0] == minDist)
                {
                    if (factory[i][1] >= factory[minDistFactoryID][1])
                    {
                        minDistFactoryID = i;
                        minDistRobotID = nearestRobot[1];
                    }
                }
            }
            --factory[minDistFactoryID][1];
            result += minDist;
            repaired.insert(minDistRobotID);
            for (auto &heap : nearestRobots)
            {
                while (!heap.empty())
                {
                    if (repaired.count(heap.top()[1]))
                    {
                        heap.pop();
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }
        return result;
    }

    class Compare
    {
    public:
        bool operator()(vector<int> &l, vector<int> &r)
        {
            if (l[0] == r[0])
            {
                return l[1] < r[1];
            }
            return l[0] > r[0];
        }
    };
};